/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-11-15
 * Time: 21:52
 */


// 2609. 最长平衡子字符串

class Solution {

    //动态规划版本(不如题解快)

    public int findTheLongestBalancedSubstring(String s) {
        //我们要返回的是s中的最长平衡子字符串的长度

        // 子字符串中 所有的 0 都在 1 之前
        // 且其中 0 的数量等于 1 的数量，
        // 这就是 平衡子字符串
        // 空子字符串也视作平衡子字符串
        // 子字符串是字符串中的一个  连续  字符序列。

        //题目规定s这个字符串的长度是大于1的

        int len=s.length();

        //有什么想法呢？
        //感觉和回文子串有点像，让左边的为0，右边的为1
        //不如试试动态规划：
        int[] dp=new int[len];
        //dp[i]的含义：以i下标的字符作为平衡串的中心 然后向2边扩散所找到的最长的平衡子串的长度
        dp[0]=0;

        for(int i=1;i<len;i++){
            int j=i-1;
            //有点类似于 00  01  11 ，现在的i和j就是在中间的这个位置(就这么找)
            //有一种从中心扩散的感觉
            int ret=i;//i的值最好还是别动

            while(j>=0 && ret<len){
                //差点忘记了，这里的是字符0，和字符1
                if(s.charAt(j)=='0' && s.charAt(ret)=='1'){
                    //没找到一对就让 ： dp[i]+=2
                    dp[i]+=2;
                    j--;
                    ret++;
                }else{
                    break;
                }
            }
        }


        //找到dp数组中的最大子字符串的长度值
        int maxvalue=0;
        for(int i=0;i<len;i++){
            if(dp[i]>maxvalue){
                maxvalue=dp[i];
            }
        }

        return maxvalue;
    }
}




// 2609. 最长平衡子字符串

class Solution2 {
    public int findTheLongestBalancedSubstring(String s) {
        //简单看了一下题解，确实有优化的空间，要好好再想一下
        //感觉应该是，来遍历s这个字符串的过程中，标记 字符0和字符1的个数关系 每次进行更新求解
        int len=s.length();
        int[] arr=new int[2];
        //arr[0]用来存放此次有效的字符0的个数
        //arr[1]用来存放此次有效的字符1的个数
        int maxvalue=0;// 用来存放平衡子字符串的最长长度值

        //遍历字符串s
        for(int i=0;i<len;i++){

            char ch=s.charAt(i);//获取s中i下标的字符

            if(ch=='0'&&arr[1]==0){
                //1.字符0的前面不存在字符1
                // 符合条件，正常让arr[0]+=1
                arr[0]+=1;
            }else if(ch=='0'&&arr[1]!=0){
                //2.字符0的前面存在字符1
                //不符合条件，从这个字符0开始重新来过（arr[1]=0;）
                arr[1]=0;
                arr[0]=1;
            }
            if(ch=='1'&&arr[0]!=0){
                //3.字符1的前面存在字符0
                //符合条件，正常让arr[1]+=1
                arr[1]+=1;
            }else if(ch=='1'&&arr[0]==0){
                //4.字符1的前面不存在字符0
                //不符合条件，字符1不能开头，所以置为0（arr[1]=0;）
                arr[1]=0;
            }

            //对每次找到的arr[0]的值和arr[1]的值进行计算求解
            //按照题目要求，我们要找的子串中的 : 字符0的个数和字符1的个数是相等的，
            //所以我们每次需要找的是 : arr[0]和arr[1]中的较小值*2，作为此次找到的子串的长度
            int ret=2*Math.min(arr[0],arr[1]);
            if(ret>maxvalue){
                maxvalue=ret;
            }
        }

        return maxvalue;
    }
}